#pragma once

#include <functional>
#include <algorithm>
#include <vector>

namespace xtd {

/// top_selector is intended to select given number (n) of minimum (predicate less<T>)
/// or maximum (predicate greater<T>) elements from a large incoming stream (m items).
/// It requires n-elements storage; the complexity is O((m+n)log n)

template < typename T, typename P = std::less<T> >
class top_selector {
	typedef std::vector<T> vec_type;
public:
	typedef typename vec_type::size_type size_type;
	typedef typename vec_type::const_iterator const_iterator;
public:
	top_selector(P p = P()) : p_(p) 
		{ }
	void start(size_type n) {
		vec_.clear();
		vec_.reserve(n_ = n);
	}
	void push_back(T const & t) {
		if (vec_.size() < n_) {
			vec_.push_back(t);
			std::push_heap(vec_.begin(), vec_.end(), p_);
		}
		else if (p_(t, vec_[0])) {
			std::pop_heap(vec_.begin(), vec_.end(), p_);
			vec_[n_ - 1] = t;
			std::push_heap(vec_.begin(), vec_.end(), p_);
		}
	}
	size_type size() const
		{ return vec_.size(); }
	bool empty() const
		{ return vec_.empty(); }
	bool full() const
		{ return vec_.size() == n_; }
	T const & worst_selected_value() const
		{ return vec_[0]; }
	void finish() 
		{ std::sort_heap(vec_.begin(), vec_.end(), p_); }
	// these methods are allowed only after the finish
	T const & operator [] (size_type i) const
		{ return vec_[i]; }
	const_iterator begin() const
		{ return vec_.begin(); }
	const_iterator end() const
		{ return vec_.end(); }
private:
	P p_;
	vec_type vec_;
	size_type n_;
};

/* Example
#include <xtd/top_selector.h>
#include <iostream>

int main()
{
	xtd::top_selector<int> mins;
	typedef xtd::top_selector<int>::const_iterator const_iterator;

	mins.start(5);
	mins.push_back(10);
	mins.push_back(8);
	mins.push_back(11);
	mins.finish();
	std::cout << "Minimal values A:\n ( " ;
	for (const_iterator it = mins.begin(); it != mins.end(); ++it)
		std::cout << *it << ' ';
	std::cout << ")." << std::endl;

	mins.start(5);
	mins.push_back(10);
	mins.push_back(8);
	mins.push_back(11);
	mins.push_back(6);
	mins.push_back(7);
	mins.push_back(12);
	mins.push_back(13);
	mins.push_back(5);
	mins.push_back(10);
	mins.finish();
	std::cout << "Minimal values B:\n ( " ;
	for (const_iterator it = mins.begin(); it != mins.end(); ++it)
		std::cout << *it << ' ';
	std::cout << ")." << std::endl;

	xtd::top_selector<int, std::greater<int> > maxs;
	maxs.start(5);
	maxs.push_back(10);
	maxs.push_back(8);
	maxs.push_back(11);
	maxs.push_back(6);
	maxs.push_back(7);
	maxs.push_back(12);
	maxs.push_back(13);
	maxs.push_back(5);
	maxs.push_back(10);
	maxs.finish();
	std::cout << "Maximal values B:\n ( " ;
	for (const_iterator it = maxs.begin(); it != maxs.end(); ++it)
		std::cout << *it << ' ';
	std::cout << ")." << std::endl;

	return 0;
}

// Output:
// Minimal values A:
//  ( 8 10 11 ).
// Minimal values B:
//  ( 5 6 7 8 10 ).
// Maximal values B:
//  ( 13 12 11 10 10 ).
*/

} //namespace xtd
